/*
 * @lc app=leetcode.cn id=380 lang=typescript
 *
 * [380] O(1) 时间插入、删除和获取随机元素
 */

// @lc code=start
class RandomizedSet {
  data: Map<number, number>;
  rand: number[];
  constructor() {
    this.data = new Map();
    this.rand = [];
  }

  insert(val: number): boolean {
    if (this.data.has(val)) return false;
    this.data.set(val, this.rand.length);
    this.rand.push(val);
    return true;
  }

  remove(val: number): boolean {
    if (!this.data.has(val)) return false;
    let idx = this.data.get(val);
    let m = this.rand.length - 1;
    // 将需要删除的元素交换到数组末尾
    [this.rand[m], this.rand[idx]] = [this.rand[idx], this.rand[m]];
    // 交换完，要将哈希中的下标位置更新
    this.data.set(this.rand[m], m);
    this.data.set(this.rand[idx], idx);
    // 删除
    this.data.delete(val);
    this.rand.pop();
    return true;
  }

  getRandom(): number {
    let idx = (this.rand.length * Math.random()) >> 0;
    return this.rand[idx];
  }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */
// @lc code=end
